package DoExercise.HSP_ZCY.A014_贪心_总是当前的全局最优解;

import java.util.HashSet;

/**
 * 给定一个字符串str，只由‘X’和‘.’两种字符构成。
 * ‘X’表示墙，不能放灯，也不需要点亮，‘.’表示居民点，可以放灯，需要点亮
 * 如果灯放在i位置，可以让i-1，i和i+1三个位置被点亮，返回如果点亮str中所有需要点亮的位置，至少需要几盏灯
 */
public class Code02_最有效的点灯策略
{
    public static void main(String[] args)
    {
        System.out.println(minLight1("..X.X..X.XX...X."));
        //        int len = 20;
        //        int testTime = 100000;
        //        for (int i = 0; i < testTime; i++)
        //        {
        //            String test = randomString(len);
        //            int ans1 = minLight1(test);
        //            int ans2 = minLight2(test);
        //            if (ans1 != ans2)
        //            {
        //                System.out.println("oops!");
        //            }
        //        }
        //        System.out.println("finish!");
    }
    
    public static int minLight1(String road)
    {
        if (road == null || road.length() == 0) return 0;
        return process(road.toCharArray(), 0, new HashSet<>());//从第一个位置开始向后统计
    }
    
    /**
     * 1 统计所有点在哪些地方可以照亮
     * 2 统计所有照亮全部的可能
     * 3 找到最少的可能为结果
     *
     * @param str
     * @param index
     * @param lights
     * @return
     */
    public static int process(char[] str, int index, HashSet<Integer> lights)
    {
        if (index == str.length)//结束的时候
        {
            for (int i = 0; i < str.length; i++)
            {
                if (str[i] != 'X')
                {//如果存在未能照亮所有位置的情况，返回
                    if (!lights.contains(i - 1) && !lights.contains(i) && !lights.contains(i + 1))
                    {
                        return Integer.MAX_VALUE;
                    }
                }
            }
            return lights.size();//有效结果，返回实际的邓数
        } else
        {
            int no = process(str, index + 1, lights);
            int yes = Integer.MAX_VALUE;
            if (str[index] == '.')
            {
                lights.add(index);//放灯
                yes = process(str, index + 1, lights);
                lights.remove(index);
            }
            return Math.min(no, yes);
        }
    }
    
    //站在当前index选择最合适的点位
    public static int minLight2(String road)
    {
        char[] str = road.toCharArray();
        int index = 0;
        int light = 0;
        while (index < str.length)
        {
            if (str[index] == 'X')
            {
                index++;
            } else
            {
                light++;
                if (index + 1 == str.length)
                {
                    break;
                } else
                {   //index + 1是墙，下一步处理index+2
                    if (str[index + 1] == 'X')
                    {
                        index = index + 2;
                    } else//剩下的情况下一步都是处理index+2
                    {
                        index = index + 3;
                    }
                }
            }
        }
        return light;
    }
    
    // for test
    public static String randomString(int len)
    {
        char[] res = new char[(int) (Math.random() * len) + 1];
        for (int i = 0; i < res.length; i++)
        {
            res[i] = Math.random() < 0.5 ? 'X' : '.';
        }
        return String.valueOf(res);
    }
    
    
}
